package practice1_100;

public class Practice42_1 {
    public int trap(int[] height){
        int sum=0;
        //算出每个柱子左右对应的最高距离
        int[] leftMax=new int[height.length];
        int[] rightMax=new int[height.length];
        int leftTemp=Integer.MIN_VALUE,rightTemp=Integer.MIN_VALUE;
        for (int i=0;i<height.length;i++){
            if(height[i]>leftTemp) {
                leftMax[i]=height[i];
                leftTemp=height[i];
            }else {
                leftMax[i]=leftTemp;
            }
        }

        for (int i=height.length-1;i>=0;i--){
            if(height[i]>rightTemp){
                rightMax[i]=height[i];
                rightTemp=height[i];
            }else {
                rightMax[i]=rightTemp;
            }
        }

        for (int j=0;j<height.length;j++){
            if(height[j]<Math.min(leftMax[j],rightMax[j]))
                sum+=Math.min(leftMax[j],rightMax[j])-height[j];
        }
        return sum;
    }
}
